package someTestExcemple.huaweiOd.container.mapAndList;
import java.util.*;
import java.util.stream.Collectors;
//https://blog.csdn.net/guorui_java/article/details/131735787
//华为OD机试 - 路灯照明问题（Java 2024 E卷 100分）

/*一、题目描述
        在一条笔直的公路上安装了N个路灯，从位置0开始安装，路灯之间间距固定为100米。
        每个路灯都有自己的照明半径，请计算第一个路灯和最后一个路灯之间，无法照明的区间的长度和。
        二、输入描述
        第一行为一个数N，表示路灯个数，1<=N<=100000。
        第二行为N个空格分隔的数，表示路径的照明半径，1<=照明半径<=100000*100。
        三、输出描述
        第一个路灯和最后一个路灯之间，无法照明的区间的长度和。*/

/**
 * 输入
 * 3
 * 20 70 30
 * 输出
 * 10
 */
//极佳思路：
//把首尾路灯之间的公路具体化为(N-1)*100段的列表S，初始全为0，
// 表示未被照明。然后遍历每个路灯，将路灯能照到的范围内的0置位1，最后统计S中0的数量。

/**
 * 解题思路如下：
 * 获取输入的灯数量；
 * 通过Java8 Steam加载n个路灯的照明半径；
 * 定义allResList，存储每个灯的照明范围；
 * 定义maxRight，计算第一个灯和最后一个灯的距离；
 * 将每个灯的照明范围放入一个集合中（左起点，右终点）；
 * 将每个灯的照明范围按照左起点进行升序排序；
 * 先按左边最小距离排序；
 * 如果左边距离相等的情况下 按照右边距离最小的排序；
 * 当前节点和下一个节点做比较；
 * 用当前节点的右边照明范围和下一个节点的左边照明范围比较；
 * 大于的情况下 需要将下一个节点的右边距离取两个节点的最大值；
 * 说明两个节点之间存在黑暗距离；
 * 输出黑暗距离之和totalBlack；
 */
public class StreetLighting {
    public static void main(String[]  args) {
        Scanner sc = new Scanner(System.in);
        int lightNum = sc.nextInt();
        // 获取输入的灯数量
        sc.nextLine();
        // n个路灯的照明半径
        List<Integer> allLightLength =
                Arrays.stream(sc.nextLine().split(" ")).
                        mapToInt(Integer::parseInt).boxed().collect(Collectors.toList());

        // 每个灯的照明范围
        List<List<Integer>> allResList = new ArrayList<>();

        // 计算第一个灯和最后一个灯的距离
        int maxRight = (lightNum - 1) * 100;

        // 将每个灯的照明范围放入一个集合中
        for (int i = 0; i < allLightLength.size(); i++) {
            // 当前灯的照明范围，左起点，右终点
            List<Integer> currentList = new ArrayList<>();
            // 左起点，注意左边范围不要小于总范围的最小长度
            Integer left = Math.max(0, i * 100 - allLightLength.get(i));
            // 右终点，注意右边范围不要大于总范围的最大长度
            Integer right = Math.min(maxRight, i * 100 + allLightLength.get(i));
            currentList.add(left);
            currentList.add(right);
            allResList.add(currentList);
        }

        // 将每个灯的照明范围按照左起点进行升序排序
        allResList = allResList.stream().sorted((list1, list2) -> {
            Integer oneLeft = list1.get(0);
            Integer twoLeft = list2.get(0);
            // 先按左边最小距离排序
            if (!oneLeft.equals(twoLeft)) {
                return oneLeft - twoLeft;
            }
            // 如果左边距离相等的情况下  按照右边距离最小的排序
            return list1.get(1) - list2.get(1);
        }).collect(Collectors.toList());

        int totalBlack = 0;
        // 当前节点和下一个节点做比较
        for (int i = 0; i < lightNum - 1; i++) {
            List<Integer> currentList = allResList.get(i);
            List<Integer> nextList = allResList.get(i + 1);

            // 用当前节点的右边照明范围和下一个节点的左边照明范围比较
            if (currentList.get(1) >= nextList.get(0)) {
                // 大于的情况下 需要将下一个节点的右边距离取两个节点的最大值
                nextList.set(1, Math.max(currentList.get(1), nextList.get(1)));
                continue;
            }
            // 说明两个节点之间存在黑暗距离
            int currentBlackLength = nextList.get(0) - currentList.get(1);
            totalBlack += currentBlackLength;
        }

        System.out.println(totalBlack);
    }
}
